package 验证二叉搜索树;

public class Solution {
    /*
    给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
    有效 二叉搜索树定义如下：
    节点的左子树只包含 小于 当前节点的数。
    节点的右子树只包含 大于 当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。
     */

    // 全局遍历记录当前的左子树的最大值（其实就是左子树最后一个被遍历的节点）
    TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        // 递归
        // 递归参数：根节点, 上层父节点的最小值，上层父节点的最大值
        // 递归返回值：true/false
        // 递归终止条件：root == null
        // 单层递归逻辑：二叉搜索树的中序遍历一定是递增的，所以是需要保证左子树所有节点小于中间节点（根节点），右子树所有节点大于中间节点
        // 所以我们比较左子树的最大值和根节点的关系即可(最大值需要用全局遍历进行维护，不然就需要回溯很麻烦),如何发现不满足条件，就结束遍历
        return judegBST(root);
    }
    public boolean judegBST(TreeNode root){
        if (root == null)
            return true;
        // 左
        boolean left = judegBST(root.left);
        // 根
        if(pre == null || pre.val < root.val){
            pre = root;
        }else{
            return false;
        }
        // 右
        boolean right = judegBST(root.right);

        return left && right;
    }
}